#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
using namespace std;
class Solution {
    int dp[100000];
public:
    int minPathSum(vector<vector<int>>& grid) {
        dp[0] = grid[0][0];
        for (int j = 1; j < grid[0].size(); j++)
        {
            dp[j] = dp[j - 1];
            dp[j] += grid[0][j];
        }
        for (int i = 1; i < grid.size(); i++)
        {
            dp[0] += grid[i][0];
            for (int j = 1; j < grid[i].size(); j++)
            {
                dp[j] = dp[j] < dp[j - 1] ? dp[j] : dp[j - 1];
                dp[j] += grid[i][j];
            }
        }
        return dp[grid[0].size() - 1];
    }
};